//TODO: LeetCode236. 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

//!二叉树分为3种情况：
//1、搜索二叉树
//2、三叉链（有三个分别指向左右子树和父节点的指针）
//3、普通二叉树
//!找公共祖先分为3种情况
//1、p、q分别在节点x的左右子树 则x就为公共祖先
//2、p、q都在节点x的左子树 就递归到x的左子树中去找
//3、p、q都在节点x的右子树 就递归到x的右子树中去找
//4、如果p为q的祖先，则p就是p、q的公共祖先；反之亦然
//如果树是搜索二叉树 判断p、q在左子树还是右子树 可以通过p、q的key值与x的key值的大小关系来找
//如果树是三叉链 因为可以找到父节点 就可以将问题转化为两个链表找公共节点的问题

//* Ver1
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root; //自己可以当自己的祖先

        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = find(root->left, q);
        qInRight = !qInLeft;
        //^相异为真 相同为假 当该条件满足时 标明p和q不都在root的左边或不都在root的右边 即在root的两侧
        if (pInLeft ^ qInLeft) 
        {
            return root;
        }
        else if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else //else if (pInRight && qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
    }

    bool find(TreeNode* root, TreeNode* aim)
    {
        if (root == nullptr) return false;

        return root == aim 
            || find(root->left, aim)
            || find(root->right, aim);
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root; //如果p为q的祖先，则p就是p、q的最近公共祖先；反之亦然。

        //在root的左右子树中分别查找p、q的最近公共祖先
        TreeNode* leftCommonAncestor = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightCommonAncestor = lowestCommonAncestor(root->right, p, q);

        //如果左子树没找到，就说明它的最近公共祖先在右子树；反之同理
        if (leftCommonAncestor == nullptr) return rightCommonAncestor;
        if (rightCommonAncestor == nullptr) return leftCommonAncestor;
        
        //如果左子树也有最近公共祖先，右子树也有最近公共祖先，说明这两个最近公共祖先分别是p、q。即p、q分布在root的两侧
        //则root为p和q的最近公共祖先
        return root;
    }
};